package com.practice.recursive;

import java.util.HashSet;

import com.practice.util.Trie;
import com.practice.util.FileHelper;

public class Boggle {
	private final int		N = 5;
	private HashSet<String> m_words;
	
	public Boggle() {
		m_words = new HashSet<String>();
	}
	
	public static void main(String[] args) {
		String[] str = new String[]{
				"AEBOF", "TSUVW", "RFOEG", "RSOFI", "PQWRE"
		};
		new Boggle().run(str);
	}
	
	public void run(String[] str) {
		char[][] cs = new char[N][N];
		boolean[][] used = new boolean[N][N];
		m_words.clear();
		
		Trie trie = new Trie();
		String dictionary = FileHelper.readFile("src/test/resources/english-dict.txt");
		for (String word : dictionary.split("\n")) {
			if (word.length() > 0) trie.addWord(word.toLowerCase());
		}
		
		for (int i=0; i<N; i++) {
			cs[i] = str[i].toLowerCase().toCharArray();
		}
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				dfs("", cs, i, j, used, trie);
			}
		}
		
		System.out.println("Find " + m_words.size() + " words.");
	}
	
	private void dfs(String cur, char[][] cs, int i, int j, boolean[][] used, Trie node) {
		if (i<0 || i>N-1 || j<0 || j>N-1 || used[i][j]) return;
		String next = cur + cs[i][j];
		node = node.getNode(cs[i][j]);
		if (node == null) return;
		
		used[i][j] = true;
		if (node.isWord() && !m_words.contains(next)) {
			m_words.add(next);
			System.out.println(next);
		}
		
		dfs(next, cs, i-1, j-1, used, node);
		dfs(next, cs, i, j-1, used, node);
		dfs(next, cs, i+1, j-1, used, node);
		dfs(next, cs, i-1, j, used, node);
		dfs(next, cs, i+1, j, used, node);
		dfs(next, cs, i-1, j+1, used, node);
		dfs(next, cs, i, j+1, used, node);
		dfs(next, cs, i+1, j+1, used, node);
		used[i][j] = false;
	}
}
